//
//$Id: re.cpp 687 2011-03-13 12:21:29Z Andrew.Tsyganov $
#include "stdafx.h"

#include "include/re.h"
#include "include/utils.h"
#include "include/sets.h"
#include "contrib/rapidxml/rapidxml.hpp"
#include "contrib/rapidxml/rapidxml_print.hpp"
#include <algorithm>

using namespace std;
using namespace rapidxml;

// Default constructor
RE::RE() 
{ 
	name_        = "";
	symbols_num_ = 0; 
	epsilon_     = kREDefaultEpsilonName; 
	infix_       = "";
};

// Manual construction 
RE::RE(string const& name, u_t const symbols_num, string const& infix, string const& epsilon) 
{ 
	name_         = name;
	symbols_num_  = symbols_num; 
	infix_        = infix;
	epsilon_      = epsilon; 
	
	if (!parse())
	{
		cout << "RE::RE error: incorrect expression!" << endl;
		clear();
	};
};

// Construction from xml file
RE::RE(string const& file) 
{ 
	if (!load_XML(file))
	{
		clear();
	}
};

// Copy constructor
RE::RE(RE const& re)
{
	name_        = re.name_;
	symbols_num_ = re.symbols_num_;
	epsilon_     = re.epsilon_;
	
	symbols_     = re.symbols_;
	infix_        = re.infix_;
	postfix_      = re.postfix_;
}

// (Re-)initialize already constructed rational expression
bool RE::init(std::string const& name, u_t const symbols_num, string const& infix, string const& epsilon)
{
	name_         = name;
	symbols_num_  = symbols_num; 
	epsilon_      = epsilon; 

	symbols_.clear();
	postfix_.clear();

	infix_        = infix;

	if (!parse())
	{
		cout << "RE::init error: incorrect expression!" << endl;
		clear();
		return false;
	};

	return true;
}

// Clear rational expression
void RE::clear()
{
	name_        = "";
	symbols_num_ = 0;
	infix_       = "";
	epsilon_     = kREDefaultEpsilonName;

	symbols_.clear();
	postfix_.clear();
}

bool RE::operand(string s) const
{
	if (s == "(") return false;
	if (s == ")") return false;
	if (s == "+") return false;
	if (s == ".") return false;
	if (s == "*") return false;
	
	return true;
}

bool RE::operand(u_t code) const
{
	if (code < symbols_num_ + 2)
	{
		return true;
	}
	else
	{
		return false;
	}
}

int RE::priority(string s) const
{
	if (s == "(") return 0;
	if (s == "+") return 1;
	if (s == ".") return 2;
	if (s == "*") return 3;

    cout << "RE::priority: unknown operation!" << endl;
    return -1;
}

u_t RE::code(string s) const
{
	if (s == "e") return symbols_num_;
	if (s == "@") return symbols_num_ + 1;
	if (s == "+") return symbols_num_ + 2;
	if (s == ".") return symbols_num_ + 3;
	if (s == "*") return symbols_num_ + 4;

	return (u_t) atoi(s.c_str());
}

bool RE::parse()
{
	infix_.erase(remove_if(infix_.begin(), infix_.end(), isspace), infix_.end());

	size_t n = infix_.size();
    postfix_.reserve(n);

    stack<string> operations;

    for (size_t i = 0; i < n; ++i)
    {
		string s(infix_, i, 1);

        if (operand(s))
        {
            postfix_.push_back(code(s));
            continue;
        }
        
        if (s == ")")
        {
            if (operations.empty())
            {
                cout << "RE::parse error: parentheses do not match!" << endl;
                return false;
            }

            while (!(operations.top() == "("))
            {
                postfix_.push_back(code(operations.top()));
                operations.pop();
                if (operations.empty())
                {
                    cout << "RE::parse error: parentheses do not match!" << endl;
                    return false;
                }
            }
            operations.pop();
            continue;
        }

        if (operations.empty() || (s == "("))
        {
            operations.push(s);
            continue;
        }

        while (priority(s) <= priority(operations.top()))
        {
            postfix_.push_back(code(operations.top()));
            operations.pop();
            if (operations.empty())
            {
                break;
            }
        }
        operations.push(s);
    }

    while (!operations.empty())
    {
		if (operations.top() == "(")
		{
			cout << "RE::parse error: parentheses do not match!" << endl;
			return false;
		}

        postfix_.push_back(code(operations.top()));
        operations.pop();
    }

	stack<u_t> operands;

	for (u_t i = 0; i < postfix_.size(); ++i)
	{
		u_t code = postfix_[i];
		if (operand(code))
		{
			operands.push(0);
		}
		else
		{
			if ((lexeme(code) == "+") || (lexeme(code) == "."))
			{
				if (operands.size() < 2)
				{ 
					cout << "RE::parse error: the number of operations does not match the number of operands!" << endl;
					return false;
				}
				else
				{
					operands.pop();
				}
			}

			if (lexeme(code) == "*")
			{
				if (operands.size() < 1)
				{ 
					cout << "RE::parse error: the number of operations does not match the number of operands!" << endl;
					return false;
				}
			}
		}
	}

	if (operands.size() != 1)
	{
		cout << "RE::parse error: the number of operations does not match the number of operands!" << endl;
	}

	return true;
}

void RE::print_TXT(ostream& os) const
{
	u_t n = postfix_.size();
	u_t m = symbols_.size();

	cout << "Rational expression " << name_ << endl;
	cout << "Infix notation: " << infix_ << endl;
	cout << "Postfix notation: ";
	for (u_t i = 0; i < n; ++i)
	{
		cout << lexeme(postfix_[i]) << " ";
	}
	cout << endl;

	for (u_t i = 0; i < m; ++i)
	{
		cout << i << " = '" << symbols_[i] << "'" << endl;
	}
}

u_t RE::get_Symbol_ID(Label const& sym) const
{
	if (symbols_.empty())
	{
		cout << "RE::get_Symbol_ID error: symbols vector is empty!" << endl;
		return symbols_num_;
	}

	for (u_t i = 0; i < symbols_.size(); ++i)
	{
		if (symbols_[i] == sym)
		{
			return i;
		}
	}

	cout << "RE::get_Symbol_ID error: symbol not found!" << endl;
	return symbols_num_;
}

void RE::set_Symbols(vector<Label> const& vl)
{
	if ((vl.size() > 0) && (vl.size() != symbols_num_))
	{
		cout << "RE::set_Symbols error: wrong vector size!" << endl;
		return;
	}

	symbols_ = vl;
}

string RE::symbol_To_String(u_t const id, string const& pfx, Labels_Type const lt) const
{
	if (id > symbols_num_)
	{
		cout << "RE::symbol_To_String error: symbol id is out of range!" << endl;
		return "";
	}

	if (id < symbols_num_)
	{
		return symbols_.empty() ? MakeLabel(pfx, id, lt) : symbols_[id].to_String();
	}
	else
	{
		return epsilon_;
	}
}

// Load rational expression from xml file
bool RE::load_XML(string const& file)
{
	string name;
	string epsilon;
	string expression;
	u_t symbols_num;

	// process re node
	vector<char> buffer;
    xml_document<> doc;
	xml_node<>* current_node;
	xml_attribute<>* attribute;
	xml_node<>* re_node = GetNode(file, buffer, doc, kREXmlNode);

	if (re_node == NULL)
	{
		cout << "RE::load_XML error: '" << kREXmlNode << "' node is missing!" << endl;
		return false;
	}

	attribute = re_node->first_attribute(kREXmlNameAttr.c_str(), 0, false);

	if (attribute == NULL)
	{
		cout << "RE::load_XML error: attribute '" << kREXmlNameAttr << "' of '" << kREXmlNode << "' node is missing!" << endl;
		return false;
	}

	name = attribute->value();

	attribute = re_node->first_attribute(kREXmlSymbolsNumAttr.c_str(), 0, false);

	if (attribute == NULL)
	{
		cout << "RE::load_XML error: attribute '" << kREXmlSymbolsNumAttr << "' of '" << kREXmlNode << "' node is missing!" << endl;
		return false;
	}
	else
	{
		if (atoi(attribute->value()) <= 0)
		{
			cout << "RE::load_XML error: attribute '" << kREXmlSymbolsNumAttr << "' of '" << kREXmlNode << "' node is illegal!" << endl;
			return false;
		}
		else
		{
			symbols_num = atoi(attribute->value());
		}
	}

	// process expression node 
	current_node = re_node->first_node(kREXmlExpressionNode.c_str(), 0, false);

	if (current_node != NULL)
	{
		expression = current_node->value();
	}
	else
	{
		cout << "RE::load_XML error: '" << kREXmlExpressionNode << "' node is missing!" << endl;
		return false;
	}

	// process epsilon node 
	current_node = re_node->first_node(kREXmlEpsilonNode.c_str(), 0, false);

	if (current_node != NULL)
	{
		epsilon = current_node->value();
	}
	else
	{
		epsilon = kREDefaultEpsilonName;
	}

	if (!init(name, symbols_num, expression, epsilon))
	{
		return false;
	}

	// process symbols node
	current_node = re_node->first_node(kREXmlSymbolsNode.c_str(), 0, false);

	if (current_node != NULL)
	{
		vector<Label> vl;
		vl.resize(symbols_num);
		Subset s;
		s.insert_range(0, symbols_num_ - 1);

		xml_node<>* t = current_node->first_node(kREXmlSymbolNode.c_str(), 0, false);

		while (t != NULL)
		{
			attribute = t->first_attribute(kREXmlIDAttr.c_str(), 0, false);

			if (attribute == NULL)
			{
				cout << "RE::load_XML error: attribute '" << kREXmlIDAttr << "' of '" << kREXmlSymbolNode << "' node is missing!" << endl;
				return false;
			}
			
			u_t id;

			if ((atoi(attribute->value()) < 0) || ((u_t)atoi(attribute->value()) >= symbols_num_))
			{
				cout << "RE::load_XML error: attribute '" << kREXmlIDAttr << "' of '" << kREXmlSymbolNode << "' node is illegal!" << endl;
				return false;
			}
			else
			{
				id = atoi(attribute->value());
			}

			string str = t->value();
			vl[id] = str;
			s.remove(id);
			t = t->next_sibling(kREXmlSymbolNode.c_str(), 0, false);
		}

		if (!s.empty())
		{
			cout << "RE::load_XML error: one or more '" << kREXmlSymbolNode << "' nodes are missing!" << endl;
			return false;
		}

		set_Symbols(vl);
	}

	return true;
}

string RE::lexeme(u_t code) const
{
	if (code == symbols_num_)     return "e";
	if (code == symbols_num_ + 1) return "@";
	if (code == symbols_num_ + 2) return "+";
	if (code == symbols_num_ + 3) return ".";
	if (code == symbols_num_ + 4) return "*";

	return IntToString(code);
}

//EOF!

